package 算法.NiuKe.JZ;


import 算法.NiuKe.TreeNode;

import java.util.Arrays;

/**
 * @author: 谢君臣
 * @create: 2021-01-20 20:43
 * @founction:
 * 题目描述
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 * 示例1
 * 输入
 * [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
 * 返回值
 * {1,2,5,3,4,6,7}
 */
public class JZ4 {
    public static TreeNode root = null;
    public static void main(String[] args) {
        int [] pre = {1,2,3,4,5,6,7};
        int [] in = {3,2,4,1,6,5,7};
        TreeNode treeNode = reConstructBinaryTree(pre, in);
        System.out.println(treeNode.val);
    }
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode treeNode = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++){
            if (pre[0] == in[i]) {
                treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return treeNode;

//        if (pre.length<1){
//            return root;
//        }else {
//            root = new TreeNode(pre[0]);
//            createTree(root,pre,in);
//        }
//        return root;
    }
    public static void createTree(TreeNode node,int [] pre,int [] in){
        int t = getArrayaIndex(in,pre[0]); // 记录根节点的下标
        if (t>1){
            // 找到中序遍历的左半边的根节点在前序遍历的位置
            int p = getIndex(Arrays.copyOfRange(in,0,t),pre);
            node.left = new TreeNode(pre[p]);
            createTree(node.left,Arrays.copyOfRange(pre,p,pre.length) ,Arrays.copyOfRange(in,0,t));
        }else if (t==1){
            node.left = new TreeNode(in[0]);
        }
       // int m = getArrayaIndex(pre, in[t - 1], s, h); // 找到右子树的第一个点
        if (in.length-t-1>1){
            // 找到中序遍历的右半边的根节点在前序遍历的位置
            int p = getIndex(Arrays.copyOfRange(in,t+1,in.length),pre);
            node.right = new TreeNode(pre[p]);
            createTree(node.right,Arrays.copyOfRange(pre,p,pre.length) ,Arrays.copyOfRange(in,t+1,in.length));
        }else if (in.length-t-1==1){
            node.right = new TreeNode(in[t+1]);
        }
    }

    private static int getIndex(int[] in ,int[] pre) {
        for (int i = 0; i < pre.length; i++) {
            for (int j = 0; j < in.length; j++) {
                if (pre[i]==in[j]) {
                    return i;
                }
            }
        }
        return -1;
    }

    private static int getArrayaIndex(int[] in, int r) {
        for (int i = 0; i < in.length; i++) {
            if (in[i]==r)
                return i;
        }
        return -1;
    }
}
